#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 5;
int prime[N], pm;
bool isp[N];
void get_prime() {
    for (int i = 2; i < N; ++ i) {
        if (!isp[i]) prime[pm ++] = i;
        for (int j = 0; prime[j] * i < N; ++ j) {
            isp[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
int check(int x) {
    int s = x << 1;
    int num = upper_bound(prime, prime + pm, s - 1) - prime - (upper_bound(prime, prime + pm, x - 1) - prime);
    return num;
}
signed main() {
    int n, k;
    get_prime();
    cin >> n;
    while (n --) {
        int x, num = 0, k = 1;
        cin >> x;
        while (k <= x) {
            if (x & k) num += check(k); //如果x在该位上为1
            k <<= 1;
        }
        cout << num << endl;
    }
    return 0;
}